package gitdemo1.git3.demo;

import java.util.*;

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }




    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int lenA=0;
        int lenB=0;

        ListNode pa=headA.next;
        ListNode pb=headB.next;

        while (pa!=null){
            lenA++;
            pa=pa.next;
        }
        while (pb!=null){
            lenB++;
            pb=pb.next;
        }
        int len=0;

        //pa是指长的链表，pb指短的链表
        if(lenA>=lenB){
            pa=headA.next;
            pb=headB.next;
            len=lenA-lenB;
        }else {
            pa=headB.next;
            pb=headA.next;
            len=lenB-lenA;
        }
        System.out.println(pa.val);
        System.out.println(pb.val);
        while (len>0){
            pa=pa.next;
            len--;
        }
        while (pa!=pb){
            pa=pa.next;
            pb=pb.next;
        }
        System.out.println(pa.val);

        return pa;

    }

    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head,slow=head;
        while (fast.next != null && fast.next.next != null) {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                fast=head;
                while (fast != slow) {
                    fast=fast.next;
                    slow=slow.next;
                }
                return slow;
            }
        }

        return null;

    }
    //删除倒数第n个
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode newHead = new ListNode(-1);
        newHead.next=head;
        ListNode slow=newHead;
        ListNode fast=newHead;
        while (n-- > 0 ) {
            fast=fast.next;
        }
        while (fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;

        return newHead;
    }

}
